﻿using System;

namespace AlgorithmWithCS.StringAlgorithm
{
    /// <summary>
    /// 子串模式匹配算法
    /// </summary>
    public static class SubStrMatch
    {
        /// <summary>
        /// 朴素模式匹配算法
        /// 最好T(n) = O(1)，就是一开始就匹配成功。
        /// 平均T(n) = O(n + m)，每次子串首字母都与主串不匹配，这样内循环每次只执行一次，
        /// 最差T(n) = O((n - m + 1) * m)，每次子串前面都与主串匹配，只有尾字母不匹配。
        /// n为主串长度，m是子串长度
        /// </summary>
        /// <param name="s">主串</param>
        /// <param name="sub">子串</param>
        /// <returns>匹配时，返回子串首个字符在主串中的位置，否则返回-1</returns>
        public static int SimpleIndexOfSubStr(string s, string sub)
        {
            // 从主串第i = 0位置开始，与子串逐字符比较，若有不相等的字符，则i回溯到
            // 起始位置+1，j回溯到0，继续逐字符比较，直到到达字符串末尾
            int i = 0, j = 0;
            while (i < s.Length && j < sub.Length)
            {
                if (s[i] == sub[j])
                {
                    ++i;
                    ++j;
                }
                else
                {
                    i -= j - 1; // 回溯到起始位置+1
                    j = 0; // 回溯到0
                }
            }
            
            // j == sub.Length，说明所有的子串字符都已匹配到，
            // 因此就返回i - j(sub.Length)，获得起始位置，否则返回-1
            return j == sub.Length ? i - j : -1;
        }
        
        /// <summary>
        /// KMP模式匹配算法
        /// 最好最好时间复杂度都差不多，很稳定
        /// T(n) = O(n + m)
        /// n是主串长度，m是子串长度
        /// </summary>
        /// <param name="s">主串</param>
        /// <param name="sub">子串</param>
        /// <returns>匹配时，返回子串首个字符在主串中的位置，否则返回-1</returns>
        public static int KMPIndexOfSubStr(string s, string sub)
        {
            // 算法实际上是对朴素匹配的改进，去除了很多不必要的匹配。
            // 考虑一种情况，如果子串大部分与主串匹配，那么下一次匹配的位置，就可以跳过
            // 大部分不必要的匹配，而直接从主串的下一个位置开始
            // 举例来说：主串：abcabcabx
            //         子串：abcx
            // 按照朴素匹配的话，则是如下步骤
            // 1. abcabcabx
            //    abcx
            // 2. abcabcabx
            //     abcx
            // 3. abcabcabx
            //      abcx
            // 4. abcabcabx
            //       abcx
            // 可以看到，2，3步骤都是没有必要的匹配
            // 假设改主串为S，子串为T，那么观察可得
            // T[0] != T[1] != T[2] != T[3]
            // 又因为
            // T[0] = S[0] T[1] = S[1] T[2] = S[2] T[3] != S[3]
            // 因此实际上T[0] != T[1] == S[1]
            //         T[0] != T[2] == S[2]
            // T[0]和T[1] T[2]都不等，而T[1] T[2]和S[1] S[2]相等，
            // 那么自然没必要比较T[0]和S[1] S[2]的情况，肯定不相等，这部分
            // 就可以直接跳过
            // 这就是KMP算法的核心思路，而到底跳过多少，就要根据子串前后缀的相似程度来决定了
            // 具体来说，可以构造一个子串T每个下标对应的函数，用于获取当该下标对应的字符与主串不
            // 匹配的时候，新的子串起始下标是多少。
            // next[j] = {
            //  -1,                                                         j == 0（这个是一个特殊值，用来保证首字符不匹配的时候
            //                                                              ，主串指针能增加，继续往后面匹配）
            // Max{k | 0 < k < j, 'p_{0}...p_{k-1}' == 'p_{j-k+1}p_{j-1}'}  集合不为空（这里实际上就是前后缀相等的最大字符个数）
            // 0,                                                           otherwise
            // }

            // 构造next函数
            int[] GetNext(string T)
            {
                var next = new int[T.Length];
                
                // 这里关键就是计算前后缀相同字符的个数
                // 具体思路就是两个指针，一个遍历前缀，一个遍历后缀，
                int p = -1, q = 0;
                next[0] = -1;
                while (q < T.Length - 1)
                {
                    if (p == -1 || T[p] == T[q])
                    {
                        ++p;
                        ++q;
                        if (T[p] != T[q]) // 如果当前字符与前缀字符不同
                        {
                            next[q] = p;
                        }
                        else // 如果相同，直接使用前缀字符
                        {
                            next[q] = next[p];
                        }
                    }
                    else
                    {
                        // 回溯p
                        p = next[p];
                    }
                }

                return next;
            }

            var next = GetNext(sub);
            
            // 有了next函数，剩下的就是和朴素匹配差不多
            // 只是当不匹配的时候，i不用回溯，j根据next调整
            // 另外要考虑首字符就不匹配的时候，需要调整i
            int i = 0, j = 0;
            while (i < s.Length && j < sub.Length)
            {
                if (j == -1 || s[i] == sub[j])
                {
                    ++i;
                    ++j;
                }
                else
                {
                    j = next[j];
                }
            }

            return j == sub.Length ? i - j : -1;
        }
    }
}